home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / program / cpp112.zoo / src / hash.c < prev    next >
C/C++ Source or Header  |  1994-07-07  |  6KB  |  232 lines
  1.  
  2. /*---------------------------------------------------------------------*\
  3. |                                    |
  4. | CPP -- a stand-alone C preprocessor                    |
  5. | Copyright (c) 1993 Hacker Ltd.        Author: Scott Bigham    |
  6. |                                    |
  7. | Permission is granted to anyone to use this software for any purpose    |
  8. | on any computer system, and to redistribute it freely, with the    |
  9. | following restrictions:                        |
  10. | - No charge may be made other than reasonable charges for repro-    |
  11. |     duction.                                |
  12. | - Modified versions must be clearly marked as such.            |
  13. | - The author is not responsible for any harmful consequences of    |
  14. |     using this software, even if they result from defects therein.    |
  15. |                                    |
  16. | hash.c -- maintain hash table for macro lookup            |
  17. \*---------------------------------------------------------------------*/
  18.  
  19. #include <stdlib.h>
  20. #include <string.h>
  21. #include "global.h"
  22. #include "ztype.h"
  23. #include "alloc.h"
  24.  
  25. #define hash_key(h) \
  26.     (((h)->flags & INLINE_KEY) ? (h)->_id.inline : (h)->_id.out_of_line)
  27.  
  28. #define HASH_SIZE 1009
  29.  
  30. extern char *magic_words[];
  31. extern int N_MWORDS, N_M2WORDS;
  32.  
  33. static Hash *H[HASH_SIZE];
  34.  
  35. /*
  36.    hash_id() -- compute a hash value for the identifier pointed to by |s|;
  37.    place a pointer to the first character after the identifier in |*end|.
  38.  
  39. Credit where it's due -- this hash function was originally suggested by Chris
  40.    Torek on comp.lang.c.  As an explanation of the implementation, he
  41.    offered:  "What *does* that 33 do?  I have no idea."
  42. */
  43. unsigned int hash_id(s, end)
  44.   register char *s;
  45.   char **end;
  46. {
  47.   register unsigned int h = 0;
  48.  
  49.   for (; is_ctok(*s); s++)
  50. /*    h = h * 33 + *s; */
  51.     h += (h << 5) + *s;
  52.   if (end)
  53.     *end = s;
  54.   return h % HASH_SIZE;
  55. }
  56.  
  57. /* set_key() -- set the key text of hash item |h| to |s| */
  58. static void set_key(h, s)
  59.   register Hash *h;
  60.   register char *s;
  61. {
  62.   if (strlen(s) <= 7) {
  63.     h->flags |= INLINE_KEY;
  64.     (void)strcpy(h->_id.inline, s);
  65.   } else {
  66.     h->flags &= ~INLINE_KEY;
  67.     h->_id.out_of_line = strdup(s);
  68.   }
  69. }
  70.  
  71. /* release_key() -- release the memory associated with the key for hash
  72.    item |h| */
  73. static void release_key(h)
  74.   register Hash *h;
  75. {
  76.   if (!(h->flags & INLINE_KEY))
  77.     free(h->_id.out_of_line);
  78.   h->flags |= INLINE_KEY;
  79.   h->_id.inline[0] = '\0';
  80. }
  81.  
  82. /*
  83.    hash_add() -- add to the hash table an entry for the identifier |s|, with
  84.    hash value |hv| and macro value |M|
  85. */
  86. void hash_add(s, hv, M)
  87.   char *s;
  88.   unsigned int hv;
  89.   Macro *M;
  90. {
  91.   register Hash *h = alloc_Hash();
  92.  
  93.   h->data = M;
  94.   h->next = NULL;
  95.   set_key(h, s);
  96.   h->next = H[hv];
  97.   H[hv] = h;
  98. }
  99.  
  100. /*
  101.    hash_unlink() -- destroy the hash object pointed to by |h|; return a
  102.    pointer to the hash object following |h|.  Used in hash_remove().
  103. */
  104. static Hash *hash_unlink(h)
  105.   register Hash *h;
  106. {
  107.   register Hash *hh = h->next;
  108.  
  109.   release_key(h);
  110.   free_Macro(h->data);
  111.   dealloc_Hash(h);
  112.   return hh;
  113. }
  114.  
  115. /*
  116.    hash_remove() -- remove the hash object for identifier |s|, with hash
  117.    value |hv|
  118. */
  119. void hash_remove(s, hv)
  120.   char *s;
  121.   unsigned int hv;
  122. {
  123.   register Hash *h;
  124.  
  125.   if (!H[hv])
  126.     return;
  127.   if (streq(hash_key(H[hv]), s)) {
  128.     H[hv] = hash_unlink(H[hv]);
  129.     return;
  130.   }
  131.   for (h = H[hv]; h->next; h = h->next)
  132.     if (streq(hash_key(h->next), s)) {
  133.       h->next = hash_unlink(h->next);
  134.       return;
  135.     }
  136. }
  137.  
  138. /*
  139.    magic_check() -- determine if the conditionally-active magic preprocessor
  140.    constant in hash object |h| is in fact active
  141. */
  142. static int magic_check(h)
  143.   register Hash *h;
  144. {
  145.   if (ansi && streq(hash_key(h), "__STDC__"))
  146.     return 1;
  147.   if ((get_mode() & IF_EXPR) && streq(hash_key(h), "defined"))
  148.     return 1;
  149.   if (fluff_mode && streq(hash_key(h), "__FLUFF__"))
  150.     return 1;
  151.   return 0;
  152. }
  153.  
  154. /*
  155.    lookup() -- look for the identifier |s| with hash value |hv| in the hash
  156.    table.  Return its associated macro value, or NULL if the identifier is
  157.    not present
  158. */
  159. Macro *lookup(s, hv)
  160.   register char *s;
  161.   unsigned int hv;
  162. {
  163.   register Hash *h;
  164.  
  165.   for (h = H[hv]; h; h = h->next)
  166.     if (streq(hash_key(h), s)) {
  167.       if (!(h->data->flags & MAGIC2) || magic_check(h)) {
  168.     return h->data;
  169.       } else {
  170.     return NULL;
  171.       }
  172.     }
  173.   return NULL;
  174. }
  175.  
  176. /*
  177.    hash_setup() -- initialize the hash table and add the predefined tokens
  178. */
  179. void hash_setup()
  180. {
  181.   register int i;
  182.   register Macro *M;
  183.   unsigned int hv;
  184.  
  185. #if 0
  186.   for (i = 0; i < HASH_SIZE; i++)
  187.     H[i] = NULL;
  188. #endif
  189.   for (i = 0; i < N_MWORDS; i++) {
  190.     M = mk_Macro();
  191.     M->flags = MAGIC;
  192.     if (i < N_M2WORDS)
  193.       M->flags |= MAGIC2;
  194.     hash_add(magic_words[i], hash_id(magic_words[i], NULL), M);
  195.   }
  196. }
  197.  
  198. /*
  199.    hash_clean_undef() -- remove all identifiers that were #undef'ined via -U
  200.    from the hash table
  201. */
  202. void hash_clean_undef()
  203. {
  204.   register int i;
  205.   register Hash *h;
  206.  
  207.   for (i = 0; i < HASH_SIZE; i++) {
  208.     while (H[i] && H[i]->data->flags & UNDEF)
  209.       H[i] = hash_unlink(H[i]);
  210.     if (H[i]) {
  211.       for (h = H[i]; h->next; h = h->next)
  212.     if (h->next->data->flags & UNDEF)
  213.       h->next = hash_unlink(h->next);
  214.     }
  215.   }
  216. }
  217.  
  218. /* hash_free() -- deallocate all hash objects */
  219. void hash_free()
  220. {
  221. #ifdef DEBUG    /* explicitly clean up, to check for memory leaks */
  222.   int i;
  223.   Hash *h;
  224.  
  225.   for (i = 0; i < HASH_SIZE; i++)
  226.     for (h = H[i]; h; h = hash_unlink(h))
  227.       continue;
  228.   cleanup_Hash();
  229.   cleanup_Macro();
  230. #endif
  231. }
  232.